import java.util.Arrays;

/**
 * @作者 zxy
 * @时间 2023-04-24 13:13
 * @说明 475. 供暖器
 * 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
 * 在加热器的加热半径范围内的每个房屋都可以获得供暖。
 * 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
 * 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
 * 示例 1:
 * 输入: houses = [1,2,3], heaters = [2]
 * 输出: 1
 * 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
 * 示例 2:
 * 输入: houses = [1,2,3,4], heaters = [1,4]
 * 输出: 1
 * 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
 */
public class Solution {
    public static void main(String[] args) {
        new Solution().findRadius(new int[]{1, 2, 3, 4}, new int[]{1, 4});
    }

    /**
     * 执行用时：11 ms, 在所有 Java 提交中击败了81.46%的用户
     * 内存消耗：42.9 MB, 在所有 Java 提交中击败了 91.48%的用户
     * @param houses
     * @param heaters
     * @return
     */
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int max = 0;
        int i = 0, j = 0;
        for (; i < houses.length; i++) {
            if (j + 1 < heaters.length) {
                int left = Math.abs(houses[i] - heaters[j]);
                int right = Math.abs(houses[i] - heaters[j + 1]);
                if (left < right) {
                    max = Math.max(max, left);
                } else {
                    max = Math.max(max, right);
                }
            } else {
                max = Math.max(max, houses[i] - heaters[j]);
            }
            while (i + 1 < houses.length && j + 1 < heaters.length && houses[i + 1] > heaters[j + 1]) j++;
        }
        return max;
    }
}
